from collections import defaultdict
from copy import deepcopy


class Solution:
    def findItinerary(self, tickets: list) -> list:
        mid_dict = defaultdict(list)
        for lists in tickets:
            mid_dict[lists[0]].append(lists[1])
        for key, lists in mid_dict.items():
            lists.sort(reverse=True)
        self.tar_len = len(tickets) + 1
        res = ["JFK"]
        try:
            self.search(mid_dict, res)
        except:
            return self.res

    def search(self, mid_dict, res):
        if len(res) == self.tar_len:
            self.res = res
            raise StopAsyncIteration
        targets = mid_dict[res[-1]]
        if len(targets) > 1:
            i = -1
            while True:
                try:
                    res.append(targets.pop(i))
                    self.search(deepcopy(mid_dict), res[:])
                except IndexError:
                    if i == -1:
                        targets.append(res.pop())
                    else:
                        targets.insert(i+1, res.pop())
                    i -= 1
        else:
            res.append(targets.pop())
            self.search(mid_dict, res)


class Solution:
    def findItinerary(self, tickets: list) -> list:
        mid_dict = defaultdict(list)
        for lists in tickets:
            mid_dict[lists[0]].append(lists[1])
        for key, lists in mid_dict.items():
            lists.sort(reverse=True)
        self.tar_len = len(tickets) + 1
        res = ["JFK"]
        return self.search(mid_dict, res)

    def search(self, mid_dict, res):
        if len(res) == self.tar_len:
            return res
        targets = mid_dict[res[-1]]
        if not targets:
            return None
        len_t = len(targets)
        if len_t > 1:
            i = -1
            while i >= -len_t:
                res.append(targets.pop(i))
                mid_res = self.search(mid_dict, res)
                if mid_res:
                    return mid_res
                if i == -1:
                    targets.append(res.pop())
                else:
                    targets.insert(i+1, res.pop())
                i -= 1
            return None
        else:
            res.append(targets.pop())
            mid_res = self.search(mid_dict, res)
            if not mid_res:
                targets.append(res.pop())
            return mid_res


a = Solution()
print(a.findItinerary([["MUC", "LHR"], ["JFK", "MUC"], ["SFO", "SJC"], ["LHR", "SFO"]]))
print(a.findItinerary([["JFK", "SFO"], ["JFK", "ATL"], ["SFO", "ATL"], ["ATL", "JFK"], ["ATL", "SFO"]]))
print(a.findItinerary([["JFK", "KUL"], ["JFK", "NRT"], ["NRT", "JFK"]]))
